We move from defining graph structures to actively finding efficient routes and sequences within them.

  • We have learned how to build graphs; now we learn how to find our way through them.
  • This lecture focuses on finding efficient routes and sequences within networked data structures.
  • We will explore two fundamental strategies tailored for different types of graph problems.
  • The first strategy addresses finding the shortest path in weighted graphs (Dijkstra's).
  • The second strategy addresses finding a valid sequence in directed acyclic graphs (Topological Sort).
Formal Definition: Pathfinding

Pathfinding

The process of finding a route between two points (vertices) in a graph, often optimizing for a specific criteria (e.g., shortest distance, lowest cost, or fewest edges).